class Solution {
    public int coinChange(int[] coins, int amount) {
        //dp[i]=min(dp[(i-c1)],dp[(i-c2)],dp[(i-c2)])+1
        int max = amount + 1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp,max);//可以在指定位置进行数值填充,这是给数组的每一个都放入max
        dp[0] = 0;
        /**
        [1,2,3]  6
        0---0
        1---dp[1-1]+1---1
        2---dp[2-1]+1,dp[2-2]+1---1
        3---dp[3-1]+1,dp[3-2]+1,dp[3-3]+1---1
        4---dp[4-1]+1,dp[4-2]+1,dp[4-3]+1---2
        5---dp[5-1]+1,dp[5-2]+1,dp[5-3]+1---2
        6---dp[6-1]+1,dp[6-2]+1,dp[6-3]+1---2
        当前值减去数组中的一个数，就是在上一个数的基础上+1(当前数)，如果不存在就一直是最大值
         */
        for(int i = 0;i <= amount;i++) {
            for(int j = 0;j < coins.length;j++) {
                if(coins[j] <= i) {
                    dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                } 
            }
        }
        return dp[amount]>amount ? -1:dp[amount];
    }
}